import math
import time

def max_subarray_sum(arr):
    """
    使用Kadane算法找出子数组之和的最大值
    时间复杂度: O(n)
    """
    if not arr:
        return 0
    
    max_ending_here = max_so_far = arr[0]
    
    for i in range(1, len(arr)):
        # 当前元素要么加入前面的子数组，要么重新开始
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        # 更新全局最大值
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

def test_max_subarray_sum():
    """测试子数组最大和函数"""
    test_cases = [
        ([1, -2, 3, 5, -1], 8),
        ([1, -2, 3, -8, 5, 1], 6),
        ([1, -2, 3, -2, 5, 1], 7),
        ([-2, -3, -1], -1),  # 全负数情况
        ([], 0),  # 空数组
        ([5], 5)  # 单元素
    ]
    
    print("测试子数组最大和:")
    for i, (arr, expected) in enumerate(test_cases, 1):
        result = max_subarray_sum(arr)
        status = "✓" if result == expected else "✗"
        print(f"测试用例 {i}: {arr} -> 期望: {expected}, 实际: {result} {status}")

def is_prime_naive(n):
    """
    朴素方法判断素数 - 最费时的函数
    时间复杂度: O(n)
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # 检查从3到n-1的所有奇数
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    return True

def is_prime_optimized(n):
    """
    优化后的素数判断方法
    时间复杂度: O(√n)
    """
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # 只需要检查到√n，且可以跳过偶数
    limit = int(math.sqrt(n)) + 1
    for i in range(5, limit, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def sieve_of_eratosthenes(limit):
    """
    使用埃拉托斯特尼筛法找出所有素数
    时间复杂度: O(n log log n) - 最高效的方法
    """
    if limit < 2:
        return []
    
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            # 标记i的所有倍数为非素数
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    primes = [i for i in range(2, limit + 1) if is_prime[i]]
    return primes

def print_primes(primes, primes_per_line=5):
    """按指定格式打印素数"""
    print(f"\n1~20000内的素数 (共{len(primes)}个):")
    print("=" * 60)
    
    for i in range(0, len(primes), primes_per_line):
        line = primes[i:i + primes_per_line]
        print(" ".join(f"{prime:5d}" for prime in line))

def performance_comparison():
    """性能对比测试"""
    print("性能对比测试:")
    print("-" * 40)
    
    # 测试朴素方法
    start_time = time.time()
    primes_naive = [i for i in range(2, 5000) if is_prime_naive(i)]
    naive_time = time.time() - start_time
    print(f"朴素方法 (n=5000): {naive_time:.4f}秒")
    
    # 测试优化方法
    start_time = time.time()
    primes_optimized = [i for i in range(2, 5000) if is_prime_optimized(i)]
    optimized_time = time.time() - start_time
    print(f"优化方法 (n=5000): {optimized_time:.4f}秒")
    print(f"性能提升: {naive_time/optimized_time:.2f}倍")
    
    # 测试筛法
    start_time = time.time()
    primes_sieve = sieve_of_eratosthenes(5000)
    sieve_time = time.time() - start_time
    print(f"筛法 (n=5000): {sieve_time:.4f}秒")
    print(f"性能提升: {naive_time/sieve_time:.2f}倍")

def main():
    """主函数"""
    print("素数查找程序")
    print("=" * 50)
    
    # 性能对比
    performance_comparison()
    
    # 使用最优方法（筛法）计算1~20000的素数
    print("\n计算1~20000的所有素数...")
    start_time = time.time()
    primes = sieve_of_eratosthenes(20000)
    end_time = time.time()
    
    print(f"计算完成! 耗时: {end_time - start_time:.4f}秒")
    
    # 打印结果
    print_primes(primes, 5)
    
    # 验证结果
    print(f"\n验证结果:")
    print(f"前10个素数: {primes[:10]}")
    print(f"最后10个素数: {primes[-10:]}")
    print(f"总数: {len(primes)}")
    print(f"最大素数: {primes[-1]}")

if __name__ == "__main__":
    # 运行任务1测试
    test_max_subarray_sum()
    print("\n" + "="*60 + "\n")
    
    # 运行任务2
    main()